package demo;

/**
 *   反转链表 II
 *
 * Input: head = [1,2,3,4,5], left = 2, right = 4
 * Output: [1,4,3,2,5]
 */
class Solution24 {
	public ListNode reverseBetween(ListNode head, int left, int right) {
		ListNode dummy = new ListNode(0);
		dummy.next = head;
		ListNode pre = dummy;
		for (int i = 1; i < left; i++) {
			pre = pre.next;
		}
		head = pre.next;
		for (int i = left; i < right; i++) {
			ListNode nex = head.next;
			head.next = nex.next;
			nex.next = pre.next;
			pre.next = nex;
		}

		return dummy.next;
	}
}

